package twobranchsearch.deletenode;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/03/12
 * @author 王光浩
 * @Thinking 使用递归+中序遍历
 */
public class MyMethodOne {
	public TreeNode deleteNode(TreeNode root, int key) {
		if(root==null)return null;
		if(root.val==key) {
			if(root.left==null || root.right==null)
				return root.left==null?root.right:root.left;
			else {
				TreeNode left=root.left;
				TreeNode last=root;
				while(left.right!=null) {
					last=left;
					left=left.right;
				}
				root.val=left.val;
				if(last==root)
					last.left=left.right;
				else last.right=left.right;
			}
		}
		else if(root.val>key)root.left=deleteNode(root.left,key);
		else
			root.right=deleteNode(root.right,key);
		return root;
    }
}
